# 剑指Offer题解 - Day64
# 剑指 Offer 19. 正则表达式匹配
请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。
示例 1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
1
2
3
4
5
2
3
4
5
示例 2:
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
1
2
3
4
5
2
3
4
5
s可能为空，且只包含从a-z的小写字母。p可能为空，且只包含从a-z的小写字母以及字符.和*，无连续的'*'。
分析：
总的思路应该是这样的：
- 从s[1]和p[1]开始判断，每轮添加一个字符并判断是否能匹配，直至添加完整个字符串s和p。
- 如果s[1-i]和p[1-i]是匹配的，那么添加下一个字符会出现两种情况：
- 添加字符s[i + 1]是否匹配？
- 添加字符p[i + 1]是否匹配？
- 由此可见，此题可以使用动态规划求解。
问题来到了动态规划转移方程如何确定。
首先，我们规定dp[i][j]代表字符串 s 的前 i 个字符和 p 的前 j 个字符能否匹配。
由于 dp[0][0]代表的是空字符的状态， 因此 dp[i][j]对应的添加字符是 s[i - 1]和 p[j - 1]。dp[i][j] 要想成立，取决于p[j - 1] 是否为* ，因为表示匹配零个或多个字符。
- 当
p[j - 1] === '*'时，以下情况为true时，dp[i][j]为true。dp[i][j - 2]****。那么p[j - 2]p[j - 1]就相当于p[j - 2]*。此时*意味着出现0次。那么p[j - 2]出现0次，就是匹配的。dp[i - 1][j]且s[i - 1] === p[j - 2]****。那么p[j - 2]p[j - 1]就相当于p[j - 2]p[j - 2]，此时*意味着多出现一次，就是匹配的。dp[i - 1][j]且p[j - 2] === '.'****。那么p[j - 2]p[j - 1]就相当于..，此时*意味着多出现一次，就是匹配的。
- 当
p[j - 1] !== '*'时，以下情况为true时，dp[i][j]为true。dp[i - 1][j - 1]且s[i - 1] === p[j - 1]。意味着s[i - 2] === p[i - 2]且s[i - 1] === p[i - 1]，那么此时肯定是相等的。dp[i - 1][j - 1]且p[j - 1] = '.'****。意味着p[j - 1]可以是任意字符，当然可以是s[i - 1]，那么此时就是匹配的。
总的来看，通过判断p的最后一个字符是否等于'*' ，来决定如何转移状态。当等于'*' 时，因为可以出现零次或者多次，所以需要判断上个字符p[j - 2]与上一个状态的关系。当不等于'*' 时，需要判断当前字符p[j - 1]与s[i - 1] 的关系。
还需要初始化dp矩阵首行，防止状态转移索引越界。
dp[0][0] = true****。也就是说两个空字符串是可以匹配的。dp[0][j] = dp[0][j - 2]且p[j - 1] === '*'****。因为首行s为空字符串，因此当p的偶数位为*时才能够匹配。此时*意味着前面的字符出现0次，也就是p的奇数位出现0次。所以将p的偶数位置为*。
最后返回矩阵右下角字符即可。
# 动态规划
/**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function(s, p) {
const m = s.length + 1;
const n = p.length + 1;
const dp = Array.from({ length: m }, () => Array.from({ length: n }).fill(false));
dp[0][0] = true;
for(let j = 2; j < n; j += 2) {
dp[0][j] = dp[0][j - 2] && p[j - 1] === '*';
}
for(let i = 1; i < m; i++) {
for(let j = 1; j < n; j++) {
if (p[j - 1] === '*') {
dp[i][j] = dp[i][j - 2] || dp[i - 1][j] && (s[i - 1] === p[j - 2] || p[j - 2] === '.')
} else {
dp[i][j] = dp[i - 1][j - 1] && (s[i - 1] === p[j - 1] || p[j - 1] === '.')
}
}
}
return dp[m - 1][n - 1];
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
- 时间复杂度 O(mn)。
- 空间复杂度 O(mn)。
# 总结
本题考查动态规划的应用。难度系数是困难。本题的难点在于如果转义状态。通过判断p的最后一个字符是否为* ，衍生出两种状态。
复杂度方面，需要遍历整个dp矩阵，因此时间复杂度是O(mn) ，而dp矩阵需要占用额外的O(mn) 空间。